package Map;

public class MyHashMap {
    // 使用 Node 表示 哈希表 中的链表节点.
    static class Node{
        public int key;
        public int value;
        public Node next;
        public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }

    // 一般来说这个数组的长度的设定也是有技巧的.
    // 一个典型的做法是选择素数作为数组的长度. 减少哈希冲突的概率.
    private Node[] table=new Node[1001];
    private int size;
    // 设定哈希函数. 把 key 转成数组下标.
    private int hashCode(int key){
        return key%table.length;
    }

    // 哈希表的核心操作
    // 插入/修改键值对
    public void put(int key,int value){
        // 1. 根据参数 key, 计算出下标位置.
        int index=hashCode(key);
        // 2. 遍历链表, 看一下 key 是否是在链表中已经存在.
        //    如果存在, 就修改对应的 value.
        Node head=table[index];
        for(Node cur=head;cur!=null;cur=cur.next){
            if (cur.key==key){
                cur.value=value;
                return;
            }
        }
        // 3. 如果不存在, 直接插入; 按照头插的方式.
        Node newNode=new Node(key,value);
        newNode.next=head;
        table[index]=newNode;
        // 4. 插入完成后, size 就要自增.
        size++;
        // 5. 扩容
        if ((double)size / table.length > 0.75) {
            resize();
        }
    }
    private void resize(){
        Node[] newTable=new Node[table.length*2];
        // 2. 搬运, 把原来 table 中的所有的链表元素都搬运过来.
        for (int i=0;i<table.length;i++){
            for (Node cur=table[i]; cur != null;cur=cur.next){
                // 根据这个节点, 创建新节点, 插入到新的数组中.
                Node newNode=new Node(cur.key,cur.value);
                int newIndex = cur.key % newTable.length;
                // 把新节点, 头插到新的链表中.
                newNode.next=newTable[newIndex];
                newTable[newIndex]=newNode;
            }
        }
        table=newTable;
    }

    // 根据键获取值
    public Integer get(int key){
        // 1. 根据 key, 计算出下标.
        int index=hashCode(key);
        // 2. 在对应的链表上找到该 key 的 value 值.
        for (Node cur=table[index];cur != null; cur = cur.next){
            if (key==cur.key){
                return cur.value;
            }
        }
        return null;
    }

    // 删除键值对. 本质上就还是链表删除.
    // 插入的时候, 一般要考虑扩容; 删除的时候, 一般不会考虑缩容~~
    public void remove (int key){
        // 1. 根据 key 找到下标.
        int index=hashCode(key);
        // 2. 针对链表删除 key 的节点.
        //  a) 先考虑链表为空的情况
        if (table[index]==null){
            return;
        }
        //  b) 先考虑是否是 头结点 的情况
        if (key==table[index].key){
            table[index]=table[index].next;
            size--;
            return;
        }
        //  c) 一般情况, 遍历链表. 遍历的同时把该节点的前一个节点, 也记录一下.
        Node prev=table[index];
        Node cur=table[index].next;
        while(cur!=null){
            if (key==cur.key){
                prev.next=cur.next;
                size--;
                return;
            }
            prev=cur;
            cur=cur.next;
        }
    }
}
